﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Algorithm.Struct;
using Algorithm.SortAlgorithm;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] random = Helper.RandomIntArray(15, 1, 100);
            //Console.WriteLine("Old");
            //Helper.PrintArray<int>(random);
            //long tick = DateTime.Now.Ticks;
            ////InsertSort.InsertSortArray<int>(random);
            ////MergeSort.MergeSortArray<int>(random,0,random.Length -1);
            ////BubbleSort.BubbleSortArray<int>(random);
            ////HeapSort.HeapSortArray<int>(random);

            //Helper.PrintArray(random);
            //MinHeapSort<int> min = new MinHeapSort<int>(random);
            //var result = min.HeapSortArray();
            //Helper.PrintArray(result);
            //List<code> codes = new List<code>();
            //          code  code = new SortAlgorithm.code(){ c='f', f=5};
            //codes.Add(code);
            //            code = new SortAlgorithm.code(){ c='e', f=9};
            //codes.Add(code);
            //code = new SortAlgorithm.code() { c = 'c', f = 12 };
            //codes.Add(code);
            //             code = new SortAlgorithm.code(){ c='b', f=13};
            //codes.Add(code);
            //            code = new SortAlgorithm.code(){ c='d', f=16};
            //codes.Add(code);
            //            code = new SortAlgorithm.code(){ c='a', f=45};
            //codes.Add(code);
            //var res = HuffMan.HuffManCoding(codes.ToArray());
            //Task t1= new Task(){ BeforeThisIndex=4,Punishment =70};
            //Task t2= new Task(){ BeforeThisIndex=2,Punishment =60};
            //Task t3= new Task(){ BeforeThisIndex=4,Punishment =50};
            //Task t4= new Task(){ BeforeThisIndex=3,Punishment =40};
            //Task t5= new Task(){ BeforeThisIndex=1,Punishment =30};
            //Task t6= new Task(){ BeforeThisIndex=4,Punishment =20};
            //Task t7= new Task(){ BeforeThisIndex=6,Punishment =10};

            //TaskScheduling.Schedul(t1, t2, t3, t4, t5, t6, t7);
            //QuickSort.QuickSortArray<int>(random);
            //long time = DateTime.Now.Ticks - tick;
            //Console.WriteLine();
            //Console.WriteLine("New start tick:" + tick);
            //Helper.PrintArray<int>(random);
            //Console.WriteLine();
            //Console.WriteLine("ticks:" + time);
            //TestRBTreeInsert();
            //TestMatrix();
            //TestBST();
            //string s1 = "BDCABA";
            //string s2 = "ABCBDAB";
            //var res = TestLCS(s2, s1);
            //Console.WriteLine(res);
            //res = TestLCS(s1, s1);
            //Console.WriteLine(res);
            //res = TestLCS(s2, s2);
            //Console.WriteLine(res);

            //RealBTree<char> Btree = RealBTree<char>.CreateRealBTree(3);
            //Btree.B_Tree_Insert('a');
            //Btree.B_Tree_Insert('b');
            //Btree.B_Tree_Insert('c');
            //Btree.B_Tree_Insert('d');
            //Btree.B_Tree_Insert('e');
            //Btree.B_Tree_Insert('f');
            ////Btree.B_Tree_Insert('g');
            //Btree.B_Tree_Del(Btree.Root,'b');
            //Btree.B_Tree_Del(Btree.Root, 'e');
            //Btree.B_Tree_Del(Btree.Root, 'd');
            //TestGraph_MST_KRUSKAL();

            TestDijkstra();
            Console.ReadKey();
        }


        public static void TestBinTree()
        {


            //BinTree<string> one = new BinTree<string>();

            BinTree<string> two = new BinTree<string>();
            two.Data="Two";

            BinTree<string> three = new BinTree<string>();
            three.Data="three";

            BinTree<string> four = new BinTree<string>();
            four.Data="four";

            two.LeftNode = three;
            two.RightNode = four;

            BinTree<string> five = new BinTree<string>();
            five.Data = "five";

            BinTree<string> six = new BinTree<string>();
            six.Data ="six";


            BinTree<string> seven = new BinTree<string>();
            seven.Data = "seven";

            five.LeftNode = six;
            five.RightNode = seven;

            BinTree<string> tree = new BinTree<string>();
            tree.Data = "root";

            tree.LeftNode = two;
            tree.RightNode = five;

            BinTreeHelper.AfterIterateNonRecursion<string>(tree, (b) => {Console.Write("  {0}  ",b.Data); });
            Console.WriteLine();
            BinTreeHelper.AfterIterateNonRecursion1<string>(tree, (b) => { Console.Write("  {0}  ", b.Data); });
        }

        public static void TestBellman_Ford()
        {
            GraphNode<int> node1 = new GraphNode<int>();
            node1.Id = 1;

            GraphNode<int> node2 = new GraphNode<int>();
            node2.Id = 2;

            GraphNode<int> node3 = new GraphNode<int>();
            node3.Id = 3;

            GraphNode<int> node4 = new GraphNode<int>();
            node4.Id = 4;

            GraphNode<int> node5 = new GraphNode<int>();
            node5.Id = 5;

            Graph<GraphNode> graph = new Graph<GraphNode>("Test", true);

            graph.AddEdge(new GraphEdge() { FirstNode = node1, SecondNode = node2, Weight = 10 });

            graph.AddEdge(new GraphEdge() { FirstNode = node2, SecondNode = node3, Weight = 1 });

            graph.AddEdge(new GraphEdge() { FirstNode = node1, SecondNode = node5, Weight = 5 });

            graph.AddEdge(new GraphEdge() { FirstNode = node2, SecondNode = node5, Weight = 2 });

            graph.AddEdge(new GraphEdge() { FirstNode = node5, SecondNode = node2, Weight = 3 });

            graph.AddEdge(new GraphEdge() { FirstNode = node3, SecondNode = node4, Weight = 4 });

            graph.AddEdge(new GraphEdge() { FirstNode = node4, SecondNode = node3, Weight = 6 });

            graph.AddEdge(new GraphEdge() { FirstNode = node5, SecondNode = node4, Weight = 2 });

            graph.AddEdge(new GraphEdge() { FirstNode = node5, SecondNode = node3, Weight = 9 });

            graph.AddEdge(new GraphEdge() { FirstNode = node4, SecondNode = node1, Weight = 7 });

            GrapHelper.Bellman_Ford<int>(graph, node1);
        }

        public static void TestDijkstra()
        {
            GraphNode<int> node1 = new GraphNode<int>();
            node1.Id = 1;

            GraphNode<int> node2 = new GraphNode<int>();
            node2.Id = 2;

            GraphNode<int> node3 = new GraphNode<int>();
            node3.Id = 3;

            GraphNode<int> node4 = new GraphNode<int>();
            node4.Id = 4;

            GraphNode<int> node5 = new GraphNode<int>();
            node5.Id = 5;

            Graph<GraphNode> graph = new Graph<GraphNode>("Test", true);

            graph.AddEdge(new GraphEdge() { FirstNode = node1, SecondNode = node2, Weight = 10 });

            graph.AddEdge(new GraphEdge() { FirstNode = node2, SecondNode = node3, Weight = 1 });

            graph.AddEdge(new GraphEdge() { FirstNode = node1, SecondNode = node5, Weight = 5 });

            graph.AddEdge(new GraphEdge() { FirstNode = node2, SecondNode = node5, Weight = 2 });

            graph.AddEdge(new GraphEdge() { FirstNode = node5, SecondNode = node2, Weight = 3 });

            graph.AddEdge(new GraphEdge() { FirstNode = node3, SecondNode = node4, Weight = 4 });

            graph.AddEdge(new GraphEdge() { FirstNode = node4, SecondNode = node3, Weight = 6 });

            graph.AddEdge(new GraphEdge() { FirstNode = node5, SecondNode = node4, Weight = 2 });

            graph.AddEdge(new GraphEdge() { FirstNode = node5, SecondNode = node3, Weight = 9 });

            graph.AddEdge(new GraphEdge() { FirstNode = node4, SecondNode = node1, Weight = 7 });

            GrapHelper.Dijkstra<int>(graph, node1);
        }

        public static void TestGraph_MST_KRUSKAL()
        {
            GraphNode<int> node1 = new GraphNode<int>();
            node1.Id = 1;

            GraphNode<int> node2 = new GraphNode<int>();
            node2.Id = 2;

            GraphNode<int> node3 = new GraphNode<int>();
            node3.Id = 3;

            GraphNode<int> node4 = new GraphNode<int>();
            node4.Id = 4;

            GraphNode<int> node5 = new GraphNode<int>();
            node5.Id = 5;

            GraphNode<int> node6 = new GraphNode<int>();
            node6.Id = 6;

            GraphNode<int> node7 = new GraphNode<int>();
            node7.Id = 7;

            GraphNode<int> node8 = new GraphNode<int>();
            node8.Id = 8;

            GraphNode<int> node9 = new GraphNode<int>();
            node9.Id = 9;

            Graph<GraphNode> graph = new Graph<GraphNode>("Test", false);

            graph.AddEdge(new GraphEdge() { FirstNode = node1, SecondNode = node2,Weight=4 });

            graph.AddEdge(new GraphEdge() { FirstNode = node1, SecondNode = node8, Weight = 8 });

            graph.AddEdge(new GraphEdge() { FirstNode = node2, SecondNode = node8,Weight=11 });

            graph.AddEdge(new GraphEdge() { FirstNode = node2, SecondNode = node3, Weight = 8 });

            graph.AddEdge(new GraphEdge() { FirstNode = node3, SecondNode = node9, Weight = 2 });

            graph.AddEdge(new GraphEdge() { FirstNode = node3, SecondNode = node4, Weight = 7 });

            graph.AddEdge(new GraphEdge() { FirstNode = node3, SecondNode = node6, Weight = 4 });

            graph.AddEdge(new GraphEdge() { FirstNode = node4, SecondNode = node5, Weight = 9 });

            graph.AddEdge(new GraphEdge() { FirstNode = node4, SecondNode = node6, Weight = 14 });

            graph.AddEdge(new GraphEdge() { FirstNode = node5, SecondNode = node6, Weight = 10 });

            graph.AddEdge(new GraphEdge() { FirstNode = node6, SecondNode = node7, Weight = 2 });

            graph.AddEdge(new GraphEdge() { FirstNode = node7, SecondNode = node8, Weight = 1 });

            graph.AddEdge(new GraphEdge() { FirstNode = node7, SecondNode = node9, Weight = 6 });

            graph.AddEdge(new GraphEdge() { FirstNode = node8, SecondNode = node9, Weight = 7 });

            var minTree = GrapHelper.MST_KRUSKAL<int>(graph);
        }

        public static void TestGraphDFS()
        {
            Graph<GraphNode> graph = new Graph<GraphNode>("Test", true);

            GraphNode<int> node1 = new GraphNode<int>();
            node1.Id = 1;

            GraphNode<int> node2 = new GraphNode<int>();
            node2.Id = 2;

            GraphNode<int> node3 = new GraphNode<int>();
            node3.Id = 3;

            GraphNode<int> node4 = new GraphNode<int>();
            node4.Id = 4;

            GraphNode<int> node5 = new GraphNode<int>();
            node5.Id = 5;

            GraphNode<int> node6 = new GraphNode<int>();
            node6.Id = 6;

            graph.AddEdge(new GraphEdge() { FirstNode = node1, SecondNode = node2 });

            graph.AddEdge(new GraphEdge() { FirstNode = node2, SecondNode = node5 });

            graph.AddEdge(new GraphEdge() { FirstNode = node5, SecondNode = node4 });

            graph.AddEdge(new GraphEdge() { FirstNode = node4, SecondNode = node2 });

            graph.AddEdge(new GraphEdge() { FirstNode = node1, SecondNode = node4 });

            graph.AddEdge(new GraphEdge() { FirstNode = node3, SecondNode = node5 });

            graph.AddEdge(new GraphEdge() { FirstNode = node3, SecondNode = node6 });


            graph.AddEdge(new GraphEdge() { FirstNode = node6, SecondNode = node6 });

            GrapHelper.DFS<int>(graph);
            
            //var nodes = GrapHelper.GetPathByBfs<int>(graph, node3, node6);
            //if (null != nodes)
            //{
            //    for (int i = 0; i < nodes.Count; i++)
            //    {
            //        Console.WriteLine(nodes[i].Id);
            //    }
            //}
            //else
            //{
            //    Console.WriteLine("No way");
            //}
        }

        public static void TestGraphBFS()
        {
            Graph<GraphNode> graph = new Graph<GraphNode>("Test", true);

            GraphNode<int> node1 = new GraphNode<int>();
            node1.Id = 1;

            GraphNode<int> node2 = new GraphNode<int>();
            node2.Id = 2;

            GraphNode<int> node3 = new GraphNode<int>();
            node3.Id = 3;

            GraphNode<int> node4 = new GraphNode<int>();
            node4.Id = 4;

            GraphNode<int> node5 = new GraphNode<int>();
            node5.Id = 5;

            GraphNode<int> node6 = new GraphNode<int>();
            node6.Id = 6;

            graph.AddEdge(new GraphEdge() { FirstNode=node1, SecondNode=node2 });

            graph.AddEdge(new GraphEdge() { FirstNode = node2, SecondNode = node5 });

            graph.AddEdge(new GraphEdge() { FirstNode = node5, SecondNode = node4 });

            graph.AddEdge(new GraphEdge() { FirstNode = node4, SecondNode = node2 });

            graph.AddEdge(new GraphEdge() { FirstNode = node1, SecondNode = node4 });

            graph.AddEdge(new GraphEdge() { FirstNode = node3, SecondNode = node5 });

            graph.AddEdge(new GraphEdge() { FirstNode = node3, SecondNode = node6 });


            graph.AddEdge(new GraphEdge() { FirstNode = node6, SecondNode = node6 });

            GrapHelper.BFS<int>(graph, node3);
            var nodes = GrapHelper.GetPathByBfs<int>(graph, node3, node6);
            if (null != nodes)
            {
                for (int i = 0; i < nodes.Count; i++)
                {
                    Console.WriteLine(nodes[i].Id);
                }
            }
            else
            {
                Console.WriteLine("No way");
            }

        }

        public static void TestBST()
        {
            double[] p= new double[]{0.15,0.1,0.05,0.10,0.20};

            double[] q = new double[] {0.05,0.10,0.05,0.05,0.05,0.10 };

            var root = Optimal_BST.GetBST(p, q);
            string[] str = { "k1", "k2", "k3", "k4", "k5" };
            for (int i = 0; i < root.GetLength(0); i++)
            {
                for (int j = 0; j < root.GetLength(1); j++)
                {
                    Console.Write("     " + root[i, j]);
                }
                Console.WriteLine();
            }

            var tree = Optimal_BST.CreateSearchBTreeByArray(str, p, q);
            var root1 = tree.Root;
        }

        public static string TestLCS(string str1, string str2)
        {
            var reslt = str1.ToArray().GetLCS(str2.ToArray());
            string s = new string(reslt);
            return s;
        }

        public static void TestMatrix()
        {
            double[,] t = new double[2, 3];
            double[,] t1 = new double[3, 2];

            for (int i = 0; i < 2; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    t[i, j] = 1;
                }
            }


            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 2; j++)
                {
                    t1[i, j] = i ;
                }
            }

            Matrix m1 = new Matrix(t);
            Matrix m2 = new Matrix(t1);
            Matrix m3 = new Matrix(t);
            Matrix m4 = new Matrix(t1);
            //var m3 = m1.Multiply(m2);
            var m5 = Matrix.FastMultiply(m1);
            for (int i = 0; i < m5.RowLen; i++)
            {
                for (int j = 0; j < m5.ColLen; j++)
                {
                    Console.Write(m5[i, j] + "    ");
                }
                Console.WriteLine();
            }
        }

        public static void TestAssemblyLine()
        {
            AssemblyLine line1 = new AssemblyLine();
            line1.StartTime = 2;
            line1.StationsTime = new double[]{7,9,3,4,8,4 };
            line1.EndTime = 3;

            AssemblyLine line2 = new AssemblyLine();
            line2.StartTime = 4;
            line2.StationsTime = new double[] { 8,5,6,4,5,7 };
            line2.EndTime = 2;

            double[][] moveTime = new double[][]{new double[]{2,3,1,3,4},new double[]{2,1,2,2,1}};

            TwoAssemblyLineCal cal = new TwoAssemblyLineCal(line1, line2, moveTime);
            cal.Cal();

            Console.WriteLine(cal.EndStation);
            Console.WriteLine(cal.AllTime);

            var endS = cal.EndStation;
            Console.WriteLine("line:" + endS + " ;Station:" + (cal.StationLength-1));
            for (int s = cal.StationLength - 2; s >= 0; s--)
            {
                endS = cal.Lines[endS][s];
                Console.WriteLine("line:" + endS + " ;Station:" + s);
                
            }
        }

        public static void TestRBTreeInsert()
        {
            RedBlackTreeExtend<int> rbTree = new RedBlackTreeExtend<int>(null);

            //var five = new RedBlackTreeNode<int>(5);
            //rbTree.RBInsert(five);

            //var fore = new RedBlackTreeNode<int>(4);
            //rbTree.RBInsert(fore);

            var five = new RedBlackTreeNodeExtend<int>(5);
            var four = new RedBlackTreeNodeExtend<int>(4);
            var three = new RedBlackTreeNodeExtend<int>(3);
            var two = new RedBlackTreeNodeExtend<int>(2);
            var one = new RedBlackTreeNodeExtend<int>(1);
            rbTree.RBInsert(five);
            rbTree.RBInsert(four);
            rbTree.RBInsert(three);
            rbTree.RBInsert(two);
            rbTree.RBInsert(one);


            //Console.WriteLine(rbTree.OS_Select(1).Data);
            Console.WriteLine(rbTree.OS_Rank(three));

            //rbTree.RB_Delete(five);
        }
    }
}
